package day_06;

import java.util.Arrays;

/**
 * @ClassName BinaryInsert
 * @Description TODO
 * @Author hp
 * @Date 2021/6/9 14:19
 * @Version 1.0
 **/
public class BinaryInsert {
    public static void main(String[] args) {
        int[] arr = {1, 4, 2, 7, 9, 8, 3, 6};

        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int left = 0;
            int right = i - 1;

            if(temp>arr[i-1]){
                continue;
            }
            if (temp < arr[i - 1]) {
                /*for(int j = 0;j<i;j++){
                    if(arr[i]<arr[j]){
                        System.arraycopy(arr,j,arr,j+1,i-j);
                        arr[j]=temp;
                    }
                }*/
                while (left <= right) {
                    int middle = (left + right) / 2;
                    if (temp < arr[middle]) {
                        right = middle - 1;
                    } else {
                        left = middle + 1;
                    }
                }
                System.arraycopy(arr,left,arr,left+1,i-left);
                arr[left]=temp;
            }

        }
        System.out.println(Arrays.toString(arr));
    }

}
